package _binary_tree

import common.v2.Node
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*


https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/
https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_116-%E5%A1%AB%E5%85%85%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E5%8F%B3%E4%BE%A7%E8%8A%82%E7%82%B9%E6%8C%87%E9%92%88
117. 填充每个节点的下一个右侧节点指针 II
同
116. 填充每个节点的下一个右侧节点指针


117. 填充每个节点的下一个右侧节点指针 II

给定一个 二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

示例 1：
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]

示例 2:
输入：root = []
输出：[]
 */
class leetcode_117 {
    val  leetcode116 : leetcode_116= leetcode_116()
    @Test
    fun test_1() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        val n7 = Node(7)
        root.left = n2
        root.right = n3
        n2.left = n4
        n2.right = n5
        n3.right = n7
        val actual: CharArray = leetcode116.print(leetcode116.connect(root))
        val expect: CharArray = charArrayOf('1', '#', '2', '3', '#', '4', '5', '7', '#')
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    @Test
    fun test_2() {
        val actual: CharArray = leetcode116.print(leetcode116.connect(null))
        val expect: CharArray = charArrayOf()
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }
}